Error correction codes (ECC) are employed in various industries, such as communication and storage systems, to detect and correct errors in a binary sequence transmitted through a communication channel. The ECC is typically implemented as a polynomial code over a Galois field GF(q), wherein if n is the code length (number of symbols per codeword) and a generator polynomial G(x) has degree m, there will be qn-m codewords (the number of polynomials of degree less than n that are divisible without remainder by G(x)). An example of a polynomial code is the Bose-Chaudhuri-Hochquenghem (BCH) code wherein the generator polynomial is chosen to have specific roots in an extension field in a way that achieves high Hamming distance. A polynomial code is “cyclic” if the generator polynomial G(x) divides xn−1. An important property of a cyclic code is that if any codeword of a code C is shifted left or right (multiplied by x or x−1), the result is also a codeword in C.
Two basic types of errors that can manifest in a transmitted codeword are shift errors and additive errors. A shift error typically occurs when there is a synchronization error, causing the beginning of the codeword to be detected too soon (shifted right) or too late (shifted left). An additive error typically occurs when noise corrupts a symbol of a codeword, for example, changing a “1” bit to a “0” bit in a codeword of a binary code GF(2).